package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @class Code72
 * @description 剑指 Offer 63. 股票的最大利润
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 *
 * 示例 1:
 *
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 * 示例 2:
 *
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-19 8:36
 */
public class Code72 {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7,1,5,3,6,4}));
    }

    public static int maxProfit(int[] prices) {
        int days = prices.length;
        int[][] dp = new int[days + 1][3];
        int maxProfit = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = -prices[i - 1];
        }
        for (int i = 2; i < dp.length; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][1] = Math.max(dp[j][0] + prices[i - 1], dp[i][1]);
                maxProfit = Math.max(dp[i][1], maxProfit);
                dp[i][2] = maxProfit;
            }
        }
        return maxProfit;
    }
}

/*
dp[i][j] 代表第 i 天 是买入还是卖出股票， j = 0 为买入 j = 1 为卖出 j = 2 为既没有买入也没有卖出
 */